package uestc.lj.advanced.greedy;

/**
 * 给定一个整形数组arr，其中可能有正、负、零，求其中子数组的最大异或和
 *
 * @Author:Crazlee
 * @Date:2021/12/10
 */
public class Code02_MaxEOR {

	public static int maxEOR1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// 尝试必须以arr[i]结尾的子数组，最大异或和是多少
		int ans = 0;
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j <= i; j++) {
				int sum = 0;
				for (int index = j; index <= i; index++) {
					sum ^= arr[index];
				}
				ans = Math.max(ans, sum);
			}
		}
		return ans;
	}

	public static int maxEOR2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int[] preSum = new int[arr.length];
		preSum[0] = arr[0];
		for (int i = 1; i < arr.length; i++) {
			preSum[i] = arr[i] ^ preSum[i - 1];
		}
		// 尝试必须以arr[i]结尾的子数组，最大异或和是多少
		int ans = 0;
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j <= i; j++) {
				int sum = preSum[i] ^ (j - 1 == -1 ? 0 : preSum[j - 1]);
				ans = Math.max(ans, sum);
			}
		}
		return ans;
	}


	public static class Node {
		public Node[] nexts = new Node[2];
	}

	public static class NumTrie {
		public Node head = new Node();

		public void add(int num) {
			Node cur = head;
			for (int move = 31; move >= 0; move--) {
				int path = ((num >> move) & 1);
				cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
				cur = cur.nexts[path];
			}
		}

		public int maxXor(int num) {
			Node cur = head;
			int res = 0;
			for (int move = 31; move >= 0; move--) {
				// num第move位的状态提取出来
				int path = (num >> move) & 1;

				// 最期待的位，如果是符号位，期待和自己一样，否则和自己不同
				int best = move == 31 ? path : (path ^ 1);

				// 实际要走的，如果期待的位不存在，只能走相反的
				best = cur.nexts[best] != null ? best : (best ^ 1);

				// 设置当前move位为异或的结果
				res |= (path ^ best) << move;
				cur = cur.nexts[best];
			}
			return res;
		}

	}

	public static int maxXorSubarray(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int max = Integer.MIN_VALUE;
		int eor = 0;
		NumTrie numTrie = new NumTrie();
		numTrie.add(0);
		for (int j : arr) {
			eor ^= j;
			max = Math.max(max, numTrie.maxXor(eor));
			numTrie.add(eor);
		}
		return max;
	}
}
